#include <iostream>
#include <vector>
#include <stack>
#include <string>
#include <set>
#include <algorithm>

using namespace std;

class Solution {
public:
    vector<int> dailyTemperatures(vector<int> &temperatures) {
        vector<int> ans(temperatures.size());
        stack<pair<int, int> > sta;
        for (int i = 0; i < temperatures.size(); i++) {
            int ctemp = temperatures[i];
            while (!sta.empty() && sta.top().first < ctemp) {
                int prevIndex = sta.top().second;
                ans[prevIndex] = i - prevIndex;
                sta.pop();
            }
            sta.push(make_pair(ctemp, i));
        }
        return ans;
    }
};

Solution solution;

int main() {
    vector<int> temp({73, 74, 75, 71, 69, 72, 76, 73});
    auto ans = solution.dailyTemperatures(temp);
    for (auto a: ans) cout << a << " ";
    return 0;
}